import java.util.LinkedList;
import java.util.Queue;

/**
 * 1293. 网格中的最短路径
 * https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
 */
public class Solutions_1293 {
    public static void main(String[] args) {
//        int[][] grid = {{0, 0, 0},
//                        {1, 1, 0},
//                        {0, 0, 0},
//                        {0, 1, 1},
//                        {0, 0, 0}};
//        int k = 1;  // output: 6

//        int[][] grid = {{0}};
//        int k = 1;  // output: 0

        int[][] grid = {{0, 1, 1},
                        {1, 1, 1},
                        {1, 0, 0}};
        int k = 1;  // output: -1

        int result = shortestPath(grid, k);
        System.out.println(result);
    }

    /**
     * 解题思路：状态BFS
     */
    public static int shortestPath(int[][] grid, int k) {
        int row = grid.length, col = grid[0].length;
        Queue<Node_1293> queue = new LinkedList<>();
        // 四个方向：上、下、左、右
        int[][] direct = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Node_1293[][] visited = new Node_1293[row][col];

        // 将 [0, 0] 添加到队列中，并记录下状态
        Node_1293 node = new Node_1293(0, 0, 0);
        queue.add(node);
        visited[0][0] = node;
        int res = 0;

        while (!queue.isEmpty()) {
            res ++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node_1293 cur = queue.poll();
                if (cur.i == row - 1 && cur.j == col - 1) {
                    // 到达终点，广度优先搜索中，首先到达终点的一定是最短路径
                    return res - 1;
                }
                // 向四周扩散
                for (int[] dir : direct) {
                    int m = cur.i + dir[0];
                    int n = cur.j + dir[1];
                    if (m >= 0 && n >= 0 && m < row && n < col) {
                        // 未越界，可以到达 [m, n]
                        int cnt = cur.count + grid[m][n];
                        if (cnt > k) {
                            // 无法再破除 grid[m][n] 上的障碍物
                            continue;
                        }
                        if (visited[m][n] == null || cnt < visited[m][n].count) {
                            // 关键：未访问过 [m, n],或者之前访问过，但是本次的路径到达 [m, n] 时，破除的障碍物更少
                            visited[m][n] = new Node_1293(m, n, cnt);
                            queue.add(visited[m][n]);
                        }
                    }
                }
            }
        }
        return -1;
    }
}

class Node_1293 {
    int i;  // 行索引
    int j;  // 列索引
    int count;  // 路径上已破除的障碍物数量

    Node_1293 (int i, int j, int count) {
        this.i = i;
        this.j = j;
        this.count = count;
    }
}
